package leecode;

import java.util.Arrays;

/**
 * @Classname
 * @Description TODO
 * @Date 2021/7/22 21:29
 * @Created by Alberthch
 * 题目：保持城际天际线
 */
class Solution_807 {

    public static int maxIncreaseKeepingSkyline(int[][] grid) {
        int num = 0;
        int max = 0;
        int row = grid.length;
        int col = grid[0].length;
        int[] rowMax = new int[row];
        int[] colMax = new int[col];

        for (int i = 0; i < row; i++) {
            max = findMaxValveInArray(grid[i]);
            rowMax[i] = max;

        }

        for (int i = 0; i < col; i++) {
            // 拿到每一列的数组
            int[] colArr = new int[row];
            for (int j = 0; j < row; j++) {
                colArr[j] = grid[j][i];
            }
            max = findMaxValveInArray(colArr);
            colMax[i] = max;
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                max = rowMax[i] < colMax[j] ? rowMax[i] : colMax[j];
                num += max-grid[i][j];

            }

        }

        return num;

    }

    // 找到一维数组中最大的元素并返回
    public static int findMaxValveInArray(int[] arr) {
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            max = max > arr[i] ? max : arr[i];
        }

        return max;
    }

    // 方法2
    public int Leecode(int[][] grid) {
        int N = grid.length;
        int[] rowMaxes = new int[N];
        int[] colMaxes = new int[N];

        // 求出行列的限制数组
        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c) {
                rowMaxes[r] = Math.max(rowMaxes[r], grid[r][c]);
                colMaxes[c] = Math.max(colMaxes[c], grid[r][c]);
            }

        int ans = 0;
        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c)
                ans += Math.min(rowMaxes[r], colMaxes[c]) - grid[r][c];

        return ans;
    }

    public static void main(String[] args) {
        int[][] city = new int[][]{{3,0,8,4},{2,4,5,7},{9,2,3,6},{0,3,1,0}};
        System.out.println(maxIncreaseKeepingSkyline(city));
    }
}
